package gobang;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Random;
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutionException;
import java.util.concurrent.Executor;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
import java.util.concurrent.ScheduledExecutorService;
import java.util.concurrent.TimeUnit;
import java.util.concurrent.TimeoutException;

import javafx.application.Application;
import javafx.geometry.Insets;
import javafx.scene.Scene;
import javafx.scene.canvas.Canvas;
import javafx.scene.canvas.GraphicsContext;
import javafx.scene.control.Button;
import javafx.scene.input.MouseEvent;
import javafx.scene.layout.GridPane;
import javafx.scene.paint.Color;
import javafx.scene.shape.Rectangle;
import javafx.stage.Stage;

public class Game extends Application {

	static int count = 0;

	static final byte NONE = 0;

	static final byte BLACK = 1;

	static final byte WHITE = 2;

	static final int DEFAULT_WIDTH = 15;

	static final char FIRST_ORDER = BLACK;

	static final int MAX_RETRACT_TIMES = 10;

	static final String FIRST_ORDER_DESC = "black";

	static final int CELL_WIDTH = 30;

	static final int CELL_DIAMETER = 20;

	static final Random random = new Random();

	static final ZobristHash zh = new ZobristHash();

	static final ScheduledExecutorService scheduler = Executors.newScheduledThreadPool(8);

	static class Pos implements Comparable<Pos> {
		int x;
		int y;
		byte color = NONE;
		int score;

		public Pos() {
		}

		public Pos(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public Pos(int x, int y, byte color) {
			super();
			this.x = x;
			this.y = y;
			this.color = color;
		}

		public Pos(int x, int y, byte color, int score) {
			super();
			this.x = x;
			this.y = y;
			this.color = color;
			this.score = score;
		}

		@Override
		public int compareTo(Pos p) {
			return this.score - p.score;
		}

		@Override
		public String toString() {
			return "Pos [x=" + x + ", y=" + y + ", color=" + color + ", score=" + score + "]";
		}

	}

	static class ChessStack {

		final LinkedList<Cell> list;

		final int size;

		public ChessStack(int size) {
			this.size = size;
			list = new LinkedList<>();
			list.add(new Cell(0, 0, NONE));
		}

		public ChessStack() {
			this(MAX_RETRACT_TIMES);
		}

		public void push(Cell cell) {
			if (isFull()) {
				list.removeFirst();
			}
			list.addLast(cell);
		}

		public Cell pop() {
			if (isEmpty()) {
				return null;
			} else {
				return list.removeLast();
			}
		}

		public boolean isFull() {
			return list.size() >= size << 1 + 1;
		}

		public boolean isEmpty() {
			return list.size() <= 1;
		}

		public Cell peek() {
			if (isEmpty()) {
				return null;
			} else {
				return list.getLast();
			}
		}

		public boolean hasPair() {
			return list.size() > 2;
		}
	}

	static class Cell {
		int x;
		int y;
		byte color = NONE;

		public Cell(int x, int y) {
			super();
			this.x = x;
			this.y = y;
		}

		public Cell(int x, int y, byte color) {
			super();
			this.x = x;
			this.y = y;
			this.color = color;
		}

		@Override
		public String toString() {
			return "Cell [x=" + x + ", y=" + y + ", color=" + color + "]";
		}

	}

	class Role {
		byte color = NONE;

		public Role(byte color) {
			this.color = color;
		}
	}

	static class ChessBoard {
		Cell[][] cells;

		Cell currCell;

		ChessStack latestChess;

		public ChessBoard() {
			cells = new Cell[DEFAULT_WIDTH][DEFAULT_WIDTH];
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					cells[i][j] = new Cell(i, j);
				}
			}

			latestChess = new ChessStack();
		}

		public void retract(Role role) throws ChessOrderException, RetractException {
			checkOrder(role.color);

			if (latestChess.isEmpty()) {
				throw new RetractException("no chance to retract any more!!!");
			}

			if (!latestChess.hasPair()) {
				throw new RetractException("there is no pair!!!");
			}

			reset(latestChess.pop());
			reset(latestChess.pop());

			currCell = latestChess.peek();

		}

		private void checkOrder(byte color) throws ChessOrderException, RetractException {
			if (currCell == null) {
				// 默认先下
				if (color != FIRST_ORDER) {
					throw new ChessOrderException(FIRST_ORDER_DESC + " first please!!!");
				}
			} else {
				if (color == currCell.color) {
					String s;
					if (color == BLACK) {
						s = "white";
					} else {
						s = "black";
					}
					throw new ChessOrderException("it is " + s + " order please!!!");
				}
			}
		}

		private boolean set(int x, int y, byte color)
				throws ExistChessPieceException, ChessOrderException, RetractException {
			if (cells[x][y].color != NONE) {
				throw new ExistChessPieceException();
			}

			checkOrder(color);

			cells[x][y].color = color;
			cells[x][y].x = x;
			cells[x][y].y = y;
			currCell = cells[x][y];

			pushRetractStack(currCell);

			if (checkHorizonal() || checkVertical() || checkSlash() || checkBackSlash()) {
				return true;
			} else {
				return false;
			}

		}

		private void pushRetractStack(Cell cell) {
			latestChess.push(cell);
		}

		private boolean isWin(int len) {
			return len >= 5;
		}

		boolean checkColor(int x, int y) {
			return currCell.color == cells[x][y].color;
		}

		/**
		 * \ 反斜杠
		 * 
		 */
		public int getBackSlashLen() {
			if (currCell == null) {
				return 0;
			}
			int len = 1;

			for (int i = currCell.x - 1, j = currCell.y - 1; i >= 0 && j >= 0 && checkColor(i, j); i--, j--) {
				len++;
			}

			for (int i = currCell.x + 1, j = currCell.y + 1; i < DEFAULT_WIDTH && j < DEFAULT_WIDTH
					&& checkColor(i, j); i++, j++) {
				len++;
			}
			return len;
		}

		public boolean checkBackSlash() {
			return isWin(getBackSlashLen());
		}

		/**
		 * / 正斜杠
		 * 
		 */
		public int getSlashLen() {
			if (currCell == null) {
				return 0;
			}
			int len = 1;

			for (int i = currCell.x - 1, j = currCell.y + 1; i >= 0 && j < DEFAULT_WIDTH
					&& checkColor(i, j); i--, j++) {
				len++;
			}

			for (int i = currCell.x + 1, j = currCell.y - 1; i < DEFAULT_WIDTH && j >= 0
					&& checkColor(i, j); i++, j--) {
				len++;
			}
			return len;
		}

		public boolean checkSlash() {
			return isWin(getBackSlashLen());
		}

		/**
		 * 垂直方向
		 * 
		 */
		public int getVerticalLen() {
			if (currCell == null) {
				return 0;
			}
			int len = 1;

			int i = currCell.x;
			for (int j = currCell.y + 1; j < DEFAULT_WIDTH && checkColor(i, j); j++) {
				len++;
			}

			for (int j = currCell.y - 1; j >= 0 && checkColor(i, j); j--) {
				len++;
			}

			return len;
		}

		public boolean checkVertical() {
			return isWin(getVerticalLen());
		}

		/**
		 * 水平方向
		 * 
		 */
		public int getHorizonalLen() {
			if (currCell == null) {
				return 0;
			}
			int len = 1;

			int j = currCell.y;
			for (int i = currCell.x + 1; i < DEFAULT_WIDTH && checkColor(i, j); i++) {
				len++;
			}

			for (int i = currCell.x - 1; i >= 0 && checkColor(i, j); i--) {
				len++;
			}

			return len;
		}

		public boolean checkHorizonal() {
			return isWin(getHorizonalLen());
		}

		public byte get(int x, int y) {
			return cells[x][y].color;
		}

		public void display() {
			for (int i = 0; i < DEFAULT_WIDTH; i++) {
				System.out.print("\t" + (i + 1));
			}
			System.out.println();
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				System.out.print(j + 1);
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					switch (get(i, j)) {
					case BLACK:
						System.out.print("\t" + BLACK);
						break;
					case WHITE:
						System.out.print("\t" + WHITE);
						break;
					default:
						System.out.print("\t" + NONE);
						break;
					}
				}
				System.out.println();
				System.out.println();
			}
		}

		public boolean chess(Pos pos) throws ExistChessPieceException, ChessOrderException, RetractException {
			return set(pos.x, pos.y, pos.color);
		}

		public void clear() {
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					reset(i, j);
				}
			}
		}

		private void reset(int x, int y) {
			cells[x][y].color = NONE;
		}

		private void reset(Cell cell) {
			reset(cell.x, cell.y);
		}

		public boolean rationalChess(Pos pos) {
			// System.out.println(pos.x + "," + pos.y + "=>" + pos.color);
			// try {
			// Thread.sleep(1000);
			// } catch (InterruptedException e1) {
			// e1.printStackTrace();
			// }
			try {
				boolean rs = chess(pos);
				zh.updateHashKey(pos.x, pos.y, pos.color);
				return rs;
			} catch (ExistChessPieceException | ChessOrderException | RetractException e) {
				e.printStackTrace();
				return false;
			}
		}

		public void lookback(Pos pos) {
			Cell cell = cells[pos.x][pos.y];
			if (cell.color == NONE) {
				throw new RuntimeException("no chess error");
			}
			reset(cell);
		}

		public boolean checkWin() {
			return checkBackSlash() || checkSlash() || checkVertical() || checkHorizonal();
		}

		@Override
		public String toString() {
			StringBuilder builder = new StringBuilder();
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					builder.append('\t').append(cells[i][j].color);
				}
				builder.append('\n');
			}
			return builder.toString();
		}

		public void switchPlayer() {

		}

	}

	private static String getColorDisplay(byte color) {
		switch (color) {
		case BLACK:
			return "black";
		case WHITE:
			return "white";
		default:
			return null;
		}
	}

	class BestMoves {
		List<Pos> bestMoves = new LinkedList<>();

		int bestScore = Integer.MIN_VALUE;

		public void save(Pos move) {
			if (move.score > bestScore) {
				bestScore = move.score;
			}
			bestMoves.add(move);
		}

		private void keepBest() {
			List<Pos> newBest = new ArrayList<>();
			for (Pos move : bestMoves) {
				if (move.score == bestScore) {
					newBest.add(move);
				}
			}
			bestMoves = newBest;
		}

		public Pos makeMove() {
			keepBest();
			if (bestMoves.isEmpty()) {
				throw new RuntimeException("no move");
			}

			Pos pos = bestMoves.get(random.nextInt(bestMoves.size()));
			bestMoves = new LinkedList<>();
			return pos;
		}
	}

	class Evaluate {
		// int SINGLE = 0;
		// int TWO_CLOSE = 1;
		// int TWO_OPEN = 2;
		// int TREE_CLOSE=3;
		// int FIVE;
		int[] scores = { 0, 0, 100, 700, 2000, 5000 };

		public int maxScore(ChessBoard board) {
			int[] arr = { board.getBackSlashLen(), board.getSlashLen(), board.getHorizonalLen(),
					board.getVerticalLen() };
			int max = Integer.MIN_VALUE;
			for (int i : arr) {
				if (i > max) {
					max = i;
				}
			}
			return scores[max >= 5 ? 5 : max];
		}
	}

	class AI {

		byte hashfEXACT = 0;
		byte hashfALPHA = 1;
		byte hashfBETA = 2;

		final int[][] SCORE_TABLE = { //
				{ -20, -10, 0, 0, 0, 10, 20, 10, 0, 0, 0, 0, 0, -10, -20 }, //
				{ -10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10 }, //
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //
				{ 0, 0, 0, 0, 0, 0, 0, 20, 40, 40, 40, 20, 0, 0, 0 }, //
				{ 0, 0, 0, 0, 0, 30, 40, 60, 60, 60, 60, 40, 30, 0, 0 }, //
				{ 0, 0, 0, 20, 40, 60, 80, 80, 80, 80, 80, 60, 40, 20, 0 }, //
				{ 0, 0, 0, 20, 40, 60, 80, 100, 100, 80, 60, 40, 20, 0, 0 }, //
				{ 0, 0, 0, 20, 40, 60, 80, 100, 100, 80, 60, 40, 20, 0, 0 }, //
				{ 0, 0, 0, 20, 40, 60, 80, 80, 80, 80, 60, 40, 20, 0, 0 }, //
				{ 0, 0, 0, 0, 0, 30, 40, 60, 60, 60, 60, 40, 30, 0, 0 }, //
				{ 0, 0, 0, 0, 0, 0, 0, 20, 40, 40, 40, 20, 0, 0, 0 }, //
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //
				{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 }, //
				{ -10, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -10 }, //
				{ -20, -10, 0, 0, 0, 0, 10, 20, 10, 0, 0, 0, 0, -10, -20 }//
		};

		Map<Long, Transposition> table = new HashMap<>();

		static final int MAX_SEARCH_DEPTH = 1;

		BestMoves bestMoves = new BestMoves();

		Evaluate eval = new Evaluate();

		volatile boolean isTimeout = false;

		private byte opposite(byte color) {
			if (color == BLACK) {
				return WHITE;
			} else if (color == WHITE) {
				return BLACK;
			} else {
				throw new RuntimeException("blank point");
			}
		}

		public List<Pos> getNextMoves(ChessBoard board, byte color) {
			Cell[][] cells = board.cells;
			List<Pos> moves = new ArrayList<>();
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					Cell cell = cells[i][j];
					if (cell.color == NONE) {
						Pos move = new Pos(i, j, color);
						board.rationalChess(move);
						int score = alphaBelta(board, MAX_SEARCH_DEPTH, Integer.MIN_VALUE, Integer.MAX_VALUE,
								opposite(color));
						board.lookback(move);
						move.score = score;
						moves.add(move);
					}
				}
			}

			sortMoves(moves);

			return moves;
		}

		private void sortMoves(List<Pos> moves) {
			Collections.sort(moves);
		}

		public int alphaBelta(ChessBoard board, int depth, int alpha, int belta, byte color) {
			if (isTimeout) {
				return Integer.MIN_VALUE;
			}
			Transposition tran;
			if ((tran = searchTranTable(board, depth)) != null) {
				if (tran.type == hashfEXACT) {
					return tran.value;
				} else if (tran.type == hashfALPHA) {
					return alpha;
				} else {
					return belta;
				}
			}
			if (depth <= 0 || board.checkWin()) {
				int val = evaluate(board);
				putToTranTable(board, hashfEXACT, val, depth);
				return val;
			}

			int score = Integer.MIN_VALUE;
			for (Pos move : getNextMoves(board, color)) {
				board.rationalChess(move);
				int t = -alphaBelta(board, depth - 1, -belta, -alpha, opposite(color));
				board.lookback(move);
				score = Math.max(score, t);

				if (alpha >= belta) {
					break;
				}
			}

			if (score < alpha) {
				putToTranTable(board, hashfALPHA, score, depth);
			} else if (score > belta) {
				putToTranTable(board, hashfBETA, score, depth);
			} else {
				putToTranTable(board, hashfEXACT, score, depth);
			}

			return score;
		}

		private void putToTranTable(ChessBoard board, byte type, int value, int depth) {
			table.put(zh.getZoristHash(board), new Transposition(type, value, depth));
		}

		private Transposition searchTranTable(ChessBoard board, int depth) {
			long hash = zh.getZoristHash(board);
			Transposition t = table.get(hash);
			if (t != null && t.depth > depth) {
				return t;
			} else {
				count++;
				return null;
			}
		}

		private int evaluate(ChessBoard board) {
			Cell curr = board.currCell;
			if (curr == null) {
				throw new RuntimeException("not chess for evaluate");
			}
			int moveScore = SCORE_TABLE[curr.x][curr.y];
			return moveScore + eval.maxScore(board);
		}

		public void play(ChessBoard board, GraphicsContext graph, byte color) {
			scheduler.schedule(new Runnable() {

				@Override
				public void run() {
					isTimeout = false;
				}
			}, 2, TimeUnit.SECONDS);
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					if (isTimeout) {
						randomChess(board, graph, color);
						isTimeout = false;
						return;
					}
					if (board.cells[i][j].color == NONE) {
						Pos pos = new Pos(i, j, color);
						board.rationalChess(pos);
						alphaBelta(board, MAX_SEARCH_DEPTH, Integer.MIN_VALUE, Integer.MAX_VALUE, opposite(color));
						board.lookback(pos);
						bestMoves.save(pos);
					}
				}
			}

			Pos bestMove = bestMoves.makeMove();
			System.out.println("best move is " + bestMove.x + "," + bestMove.y);
			putChess(board, graph, bestMove.x, bestMove.y, color);
			isTimeout = false;
		}

		private void randomChess(ChessBoard board, GraphicsContext graph, byte color) {
			for (;;) {
				int x = random.nextInt(DEFAULT_WIDTH);
				int y = random.nextInt(DEFAULT_WIDTH);
				if (board.cells[x][y].color == NONE) {
					putChess(board, graph, x, y, color);
					return;
				}
			}
		}

	}

	class Hum {

		public void play(ChessBoard board, GraphicsContext graph, MouseEvent value, byte color) {
			double x = value.getX() - 100 - CELL_WIDTH, y = value.getSceneY() - 100 - CELL_WIDTH;
			int xi = (int) Math.round(x / CELL_WIDTH);
			int yi = (int) Math.round(y / CELL_WIDTH);

			putChess(board, graph, xi, yi, color);
		}

	}

	class Transposition {
		byte type;
		int value;
		int depth;

		// Pos bestMove;
		public Transposition(byte type, int value, int depth) {
			super();
			this.type = type;
			this.value = value;
			this.depth = depth;
		}
	}

	static class ZobristHash {
		byte colorNum = 3;
		long[][][] zobrist;

		long hash;

		public ZobristHash() {
			zobrist = new long[DEFAULT_WIDTH][DEFAULT_WIDTH][colorNum];
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					for (int k = 0; k < colorNum; k++) {
						zobrist[i][j][k] = random();
					}
				}
			}
		}

		public long getZoristHash(ChessBoard board) {
			if (hash != 0) {
				return hash;
			}
			Cell[][] cells = board.cells;
			for (int j = 0; j < DEFAULT_WIDTH; j++) {
				for (int i = 0; i < DEFAULT_WIDTH; i++) {
					byte color = cells[i][j].color;
					hash ^= zobrist[i][j][color];
				}
			}
			return hash;
		}

		public void updateHashKey(int x, int y, byte color) {
			hash = hash ^ zobrist[x][y][color];
		}

		private long random() {
			return random.nextLong();
		}
	}

	byte currentColor = BLACK;

	boolean start = true;

	AI ai = new AI();

	Hum hum = new Hum();

	@Override
	public void start(Stage stage) throws Exception {
		ChessBoard board = new ChessBoard();
		Canvas canvas = new Canvas(CELL_WIDTH * (DEFAULT_WIDTH + 1), CELL_WIDTH * (DEFAULT_WIDTH + 1));
		GraphicsContext graph = canvas.getGraphicsContext2D();
		drawChessboard(graph);

		GridPane grid = new GridPane();
		Rectangle rec = new Rectangle(CELL_WIDTH * (DEFAULT_WIDTH + 1), CELL_WIDTH * (DEFAULT_WIDTH + 1));
		rec.setFill(Color.rgb(218, 189, 160));
		grid.setPadding(new Insets(100, 300, 100, 100));
		grid.getChildren().add(rec);
		grid.getChildren().add(canvas);

		// final byte humColor = BLACK, aiColor = WHITE;
		final byte aiColor = BLACK, humColor = WHITE;

		if (checkTurn(aiColor, currentColor)) {
			ai.play(board, graph, currentColor);
		}

		grid.setOnMouseClicked(value -> {
			if (checkTurn(currentColor, humColor)) {
				hum.play(board, graph, value, currentColor);
			}

			if (checkTurn(currentColor, aiColor)) {
				ai.play(board, graph, currentColor);
			}
		});

		Button button = new Button("start");
		grid.add(button, 100, 100);
		button.setOnAction(value -> {
			clearChessboard(graph);
		});

		Scene scene = new Scene(grid);
		stage.setScene(scene);
		stage.setTitle("line");
		stage.show();
	}

	private boolean checkTurn(byte c1, byte c2) {
		return c1 == c2;
	}

	private void clearChessboard(GraphicsContext graph) {
	}

	private void drawChess(GraphicsContext graph, int x, int y, byte color) {
		if (color == BLACK) {
			graph.setFill(Color.BLACK);
		} else if (color == WHITE) {
			graph.setFill(Color.WHITE);
		}
		graph.fillOval((x + 1) * CELL_WIDTH - CELL_DIAMETER / 2, (y + 1) * CELL_WIDTH - CELL_DIAMETER / 2,
				CELL_DIAMETER, CELL_DIAMETER);
	}

	private void putChess(ChessBoard board, GraphicsContext graph, int x, int y, byte color) {
		if (!start) {
			System.out.println("not start");
			return;
		}
		Pos pos = new Pos(x, y, color);
		try {
			if (board.chess(pos)) {
				drawChess(graph, x, y, color);
				System.out.println(getColorDisplay(color) + " wins!!!");
				currentColor = BLACK;
				start = false;
				return;
			}
			drawChess(graph, x, y, color);
			if (color == WHITE) {
				currentColor = BLACK;
			} else {
				currentColor = WHITE;
			}

		} catch (ExistChessPieceException e) {
			System.out.println("already has chess piece at " + pos.x + "," + pos.y);
		} catch (ChessOrderException e) {
			System.out.println(e.getMessage());
		} catch (RetractException e) {
			System.out.println(e.getMessage());
		}
	}

	private void drawChessboard(GraphicsContext graph) {
		for (int j = 1; j <= DEFAULT_WIDTH; j++) {
			for (int i = 1; i <= DEFAULT_WIDTH - 1; i++) {
				graph.strokeLine(i * CELL_WIDTH, j * CELL_WIDTH, (i + 1) * CELL_WIDTH, j * CELL_WIDTH);
			}
		}

		for (int j = 1; j <= DEFAULT_WIDTH - 1; j++) {
			for (int i = 1; i <= DEFAULT_WIDTH; i++) {
				graph.strokeLine(i * CELL_WIDTH, j * CELL_WIDTH, i * CELL_WIDTH, (j + 1) * CELL_WIDTH);
			}
		}

	}

	public static void main(String[] args) {
		launch(args);
		// ChessBoard board = new ChessBoard();
		// board.rationalChess(new Pos(0, 0, BLACK));
		// System.out.println(board.getBackSlashLen());
		// System.out.println(board.getSlashLen());
		// System.out.println(board.getHorizonalLen());
		// System.out.println(board.getVerticalLen());
		// System.out.println("haha");
	}
}
